package com.cat.dataStructure02;

import java.util.Arrays;

class Solution20 {
    public long maxSubarraySum(int[] nums, int k) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        long ans = Long.MIN_VALUE;
        long[] min = new long[k];
        Arrays.fill(min, Long.MAX_VALUE / 2);
        for (int i = 0; i <= n; i++) {
            int j = i % k;
            ans = Math.max(ans, prefix[i] - min[j]);
            min[j] = Math.min(min[j], prefix[i]);
        }

        return ans;
    }
}